package tree;

import commons.TreeNode;

/**
 * leet-code(543) 二叉树的直径
 *
 * @author Ringo
 * @date 2021/10/8 21:00
 */
public class DiameterOfBinaryTree {

    public static void main(String[] args) {
        TreeNode root = TreeNode.create(1)
                .left(TreeNode.create(2).left(TreeNode.create(4)).right(TreeNode.create(5)))
                .right(TreeNode.create(3));
        System.out.println(diameterOfBinaryTree(root));
    }

    private static int ans = 0;

    public static int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return ans;
    }

    public static int dfs(TreeNode x) {
        if (x == null) {
            return 0;
        }
        int left = dfs(x.left);
        int right = dfs(x.right);
        int path = left + right;
        ans = Math.max(ans, path);
        return Math.max(left, right) + 1;
    }

}
